1. Field of the Invention
The present invention generally relates to a system and method for multi-bit halftoning. In particular, the present invention is directed to a system and method for multi-bit halftoning that avoids smooth textures for intermediate levels.
2. Description of the Related Art
Generally, digital halftoning is accomplished by either bi-tonal or multi-tonal halftoning methods. In general, bi-tonal digital halftoning converts a continuous tone image into a halftone image including a pattern of equal intensity dots. Each dot within the bi-tonal halftone image either exists (black) or does not exist (white), i.e. a bi-tonal image.
More specifically, bi-tonal digital halftoning converts a plurality of digitized intensity values representing a continuous tone image into a plurality of halftone dots, where each halftone dot is either white or black and the ratio of white to black dots, in the halftone cell, is related to the magnitude of the corresponding intensity values in that region. The intensity values are typically generated by periodically sampling a continuous tone image using an optical scanner.
One method of such spatially periodic sampling would be to sample on a square grid. Each intensity value represents the image intensity in an immediate area surrounding the location within the continuous tone image from which the intensity value sample was taken. Typically, each intensity value is quantized such that the intensity corresponds to one of a plurality of levels known as gray levels. Quantization permits each intensity value to be represented by a digital value and to be processed by digital circuitry into a halftone image. For instance, if the intensity values are quantized into 256 levels, i.e., a 256 level gray scale, each of the intensity values can be represented by an eight-bit digital word.
Commonly in bi-tonal digital halftoning, intensity values are mapped into a spatial area on the halftone image known as a halftone cell. Each halftone cell includes a plurality of pixels (or dots as stated above), each having a bi-tonal value, i.e., either black or white.
In operation, a bi-tonal digital halftoning system compares each intensity value sample to an element in a matrix of modulation levels and generates a halftone pixel or dot corresponding to the comparison.
As is known in the art, the previously described halftoning process is useful in halftoning color images by repeating the bi-tonal process for each primary color, e.g., red, blue, and green, or cyan, magenta, and yellow, and, subsequently, overlaying the color halftone images with proper registration.
More and more printers are capable of printing pixels of various intensity values. The varying intensity values mean that each pixel may require more than one bit to describe its output intensity level. One halftoning process that takes advantage of this capability is called “multi-bit halftoning.” Multi-bit (i.e. multi-level) halftoning is an extension of bi-tonal halftoning. As the name implies, multi-bit halftoning replaces each black or white pixel in a bi-tonal halftone cell with a pixel having a value selected from a number of values available for each pixel. In essence, multi-bit halftoning redistributes the intensity of a single intensity value into a plurality of intensity values.
Many (output) devices (e.g., printers, displays, etc.) permit a multi-bit pixel display; multi-bit halftoning takes advantage of this capability. For example, thermal printers are capable of printing dot sizes that correspond to various pixel intensity levels.
Additionally, cathode ray tube (CRT) displays can display various pixel intensities by altering an electron beam strength incident upon each pixel within the CRT display.
Typically, output devices, such as printers, are limited as to the number of levels that they can print. In contrast, image capturing devices (e.g., scanners, etc.) can produce large numbers of output levels. Therefore, multi-bit halftoning is used to convert a large number of output levels from a capturing device into a lesser number of levels compatible with a printer. For instance, if a printer may accurately print five (5) levels while a scanner can provide 256 level intensity values, the multi-bit halftoning system must distribute the single 256 level value into one of five possible pixel levels. This is done in such a way that a region of pixels viewed from a distance appears approximately the same as the corresponding region of 256 level values.
To determine the appropriate level for each pixel in a multi-bit halftone cell, an input intensity value is compared to a number of modulation level matrices, i.e., N−1 matrices are used to generate N levels. Generally, the comparison process is similar to that used in bi-tonal halftoning except the comparison process is repeated N−1 times for N−1 matrices. As in bi-tonal halftoning, each matrix contains, as matrix elements, a number of modulation levels. The number of matrix elements is equivalent to the number of pixels in the halftone cell. The output of each comparison is a digital bit, i.e., a signal having a value of either a logical “1” or a logical “0.” The output bit value indicates whether the intensity value was greater than the modulation (e.g., threshold) level, i.e., logical “1,” or less than the modulation level, i.e., logical “0.” Each output bit is stored in an intermediate matrix. Thus, a set of N intermediate matrices containing digital bits is generated. An encoder combines the elements of the intermediate matrices to generate the pixel values for a halftone cell.
Ideally, the smaller the contrast between light and dark pixels that are used to output intermediate gray levels, the smoother and higher the quality of the output image. One multi-bit halftoning method, which relies upon this relationship, is described in U.S. Pat. No. 5,291,311, which is incorporated herein in its entirety. Using this multi-bit halftone method, gray levels, which are equal to one of the printer's output levels, are rendered using only those levels which are closest to the input gray level. Therefore, the output image from these printers at these gray levels is very smooth.
However, certain printers cannot print a uniform intermediate gray level area reliably without having some contrast between neighboring pixels. For example, some electrographic printers cannot reliably print low contrast intermediate levels. Electrographic printers use electromagnetic field to transfer toner on the paper. Low contrast level between neighboring pixels does not create an electro-magnetic field that is strong enough to provide reliable toner transfer.
One conventional method for addressing this problem is known as the “gray-on-edges” method. The gray-on-edges method places intermediate pixel values only on the edges of pixel clusters. Thus, this method makes use of the gray level capability of a printer, but still uses the lightest and darkest pixels in rendering intermediate gray levels. However, this conventional method does not provide the increased quality improvement that may be possible if the contrast levels were reduced.